#include <stdio.h>
#include <string.h>
#include <stdlib.h>
 
 
#define max(a, b) (a > b ? a : b)

char* addBinary(char *a, char *b)
{
    int alen = strlen(a);
    int blen = strlen(b);
    // 需要一个额外的位置保存'\0'，需要一个额外的位置保存可能的最高位进位
    int anslen = max(alen, blen) + 1 + 1;

    char *ans = malloc(sizeof(char) * anslen);
    ans[0] = '0';   // 默认两数相加没有最高位进位
    ans[anslen - 1] = '\0';

    int c = 0;      // 进位
    int i = alen - 1, j = blen - 1, k = anslen - 2;      // 从末尾开始各个位相加
    while (i >= 0 || j >= 0) {
        int abit = i >= 0 ? a[i] - '0' : 0;
        int bbit = j >= 0 ? b[j] - '0' : 0;
        int bitsum = abit + bbit + c;

        ans[k] = '0' + bitsum % 2;

        c = bitsum / 2;
        --i;--j;--k;
    }

    if (c != 0)
        ans[k] = '1';

    return ans[0] == '0' ? ans + 1 : ans;
}

 
int main()
{
    char a[] = "1001";
    char b[] = "101";
    char *p = addBinary(a, b);

    printf("%s\n",p);

    free(p);//释放空间
 
    return 0;
}